A known method for encrypting a sequence of data blocks consists of a Cipher Block Chaining (CBC) process where each block of plaintext is combined with the preceding ciphertext block by using XOR operation before being encrypted. Each ciphertext block is thus dependent on all plaintext blocks processed before a given block.
The CBC method requires a decryption module with a buffer able to store at least two block lengths of digital data. Furthermore, a header block with a fixed bit pattern is generally provided at the beginning of each sequence or packet of digital data. As the first block is combined with a fixed initial vector, this could result in a bit pattern recognizable in the encrypted data.
The block cipher modes of operation with chaining provide error propagation in only one direction. A “folklore” method to obtain a Bidirectional Difference Propagation (BDP) is thus to make two processing passes over the data blocks, in the two directions (first block to the last, and reverse) as described in document of George Danezis and Ben Laurie, “Minx: a simple and efficient anonymous packet format”, in Vijay Atluri, Paul F. Syverson, and Sabrina De Capitani di Vimercati, editors, WPES, pages 59-65. ACM, 2004. For both encryption and decryption, the whole sequence of blocks needs to be kept in memory, with two layers of encryption and decryption.
U.S. Pat. No. 5,799,089 discloses a system for encrypting and decrypting digital data wherein the data is divided in packets of N blocks X1 . . . XN of 2m bits, comprises an encryption device and a decryption device. The encryption device reverses the input sequence of the blocks X1 . . . XN before a XOR operation and next an encryption operation by means of an encryption algorithm E is carried out on each block of a packet. Thereby the following encrypted blocks Y1 . . . YN are formed: The encrypted blocks Y1 . . . YN are transferred by a sender in reversed sequence YN . . . Y1 to a receiver. The decryption device at the receiver obtains the original blocks X1 . . . XN by carrying out a decryption operation by means of a decryption algorithm D and next a XOR operation on each block YN . . . Y1 received to obtain the original blocks X1 . . . XN. This system applies the aforementioned Cipher Block Chaining (CBC) to a sequence of blocks in a reversed order relative to the order of the input sequence.
This block cipher mode of operation RCBC Reverse Cipher Block Chaining can be used to achieve Bidirectional Difference Propagation (BDP), when combined with another layer of encryption/decryption. With this method, encryption makes two processing passes over the data, and thus needs to keep the whole sequence of blocks in memory. However, decryption is done in one pass over the data (with two encryption layers), and only two blocks need be kept in memory.
The ciphering method BEAR and LION particularly adapted to large blocks described by Ross J. Anderson and Eli Biham “Two practical and provably secure block ciphers: BEAR and LION” and by Eli Biham, editor, “Fast Software Encryption”, 4th International Workshop, FSE '97, Haifa, Israel, Jan. 20-22, 1997, Proceedings, volume 1267 of LNCS. Springer, 1997, pages 113-120 provides BDP by using large, variable-size blocks. However both encryption and decryption need two passes over the data and memory to store the whole sequence of blocks.
Other processes called All-or-nothing-transforms are described by Ran Canetti, Yevgeniy Dodis, Shai Halevi, Eyal Kushilevitz, and Amit Sahai, “Exposure-resilient functions and all-or-nothing transforms”; in Bart Preneel, editor, EUROCRYPT, volume 1807 of LNCS, pages 453-469, Springer, 2000 and by Ronald L. Rivest. “All-or-nothing encryption and the package transform” in Eli Biham, editor, “Fast Software Encryption”, 4th International Workshop, FSE'97, Haifa, Israel, Jan. 20-22, 1997, Proceedings, volume 1267 of LNCS. Springer, 1997, pages 210-218.
These processes achieve also BDP. However, the construction according to Ronald L. Rivest “All-or-nothing encryption and the package transform” achieves Bidirectional Difference Propagation (BDP) with respect to decryption rather than encryption, it needs two levels of processing for encryption and decryption, and decryption needs memory for the whole sequence of blocks. Moreover, ciphertexts are longer than plaintexts by one block, and encryption is probabilistic, i.e., it uses an auxiliary pseudorandom generator.